package top.dprkshow.practice.graph;

import edu.princeton.cs.algs4.Stack;

/**
 * @author Kent HAN
 * @date 2021/9/14
 */
public class ReversePostOrder {
    boolean[] visited;
    Stack<Integer> reversePost;

    public ReversePostOrder(Digraph g) {
        reversePost = new Stack<>();
        visited = new boolean[g.getTotalVertices()];
    }

    public void init(Digraph g) {
        for (int i = 0; i < g.getTotalVertices(); i++) {
            if (!visited[i]) {
                dfs(g, i);
            }
        }
    }

    void dfs(Digraph g, int vertex) {
        visited[vertex] = true;
        for (Integer adjVertex : g.adj(vertex)) {
            if (!visited[adjVertex]) {
                dfs(g, adjVertex);
            }
        }
        reversePost.push(vertex);
    }
}
